package com.solming.leetcode.question;

//给你二叉树的根结点 root ，请你将它展开为一个单链表：
//
//展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
//展开后的单链表应该与二叉树 先序遍历 顺序相同。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
public class Flatten114 {

    public static void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.left);
        flatten(root.right);

        TreeNode left = root.left;
        TreeNode right = root.right;
        root.right =  left;
        root.left = null;
        //将原先的右子树接到当前右子树的末端
        TreeNode  tmpRoot = root;
        while (tmpRoot.right!=null){
            tmpRoot =  tmpRoot.right;
        }
        tmpRoot.right = right;

    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(5);
        treeNode.left.left = new TreeNode(3);
        treeNode.left.right = new TreeNode(4);
        treeNode.right.right = new TreeNode(5);
        treeNode.right.right.right = new TreeNode(6);
        flatten(treeNode);
        System.out.println();

    }


}
